package com.cqs.leetcode.link;

import com.cqs.leetcode.ListNode;

/**
 * @author lixiaowen
 * @create 2019-12-14
 */
public class SwapNodesinPairs24 {
    public ListNode swapPairs(ListNode head) {
        return revert(head,2);
    }

    /**
     * 每K各结点进行翻转 不足K个把持原序
     *
     * @param head
     * @param k
     * @return
     */
    private ListNode revert(ListNode head,final int k) {
        if (head == null || head.next == null || k == 1) return head;
        //分段处理,
        ListNode nextHead = head, start = null , end = null, preRevertTail = null;
        int count = 0;
        while (nextHead != null) {
            count = k;
            start = nextHead;
            //切分出K个结点
            while (nextHead != null && --count>=0 ){
                end = nextHead;
                nextHead = nextHead.next;
            }
            //不足K各结束
            if (count > 0) break;
            //翻转列表
            revert(start,end);
            //TODO
            ListNode tmp = start;
            start = end;
            end = tmp;
            //start和上次切分的子链表链接起来
            if (preRevertTail != null) {
                preRevertTail.next = start;
                preRevertTail = end;
            }else {
                //第一段 获得翻转后的新链表头
                head = start;
                preRevertTail = end;
            }
        }
        //不需要翻转的部分
        if (preRevertTail != null && count != 0) {
            preRevertTail.next = start;
        }
        return head;
    }

    /**
     * 翻转之后start仍是翻转之后的head
     * end 仍是翻转之后的tail
     * @param start
     * @param end
     * @return
     */
    private ListNode revert(ListNode start, ListNode end) {
        if (start == null || start. next == null) return start;
        ListNode  pre = start, post = null; start = start.next;
        pre.next = null;
        while (start != end) {
            post = start.next;
            start.next = pre;
            pre = start;
            start = post;
        }
        start.next = pre;
        return start;
    }

    public static void main(String[] args) {
        ListNode list = ListNode.randomLink(10);
        SwapNodesinPairs24 swap = new SwapNodesinPairs24();
        System.out.println("origin: " + list);
        list = swap.swapPairs(list);
//        list = swap.revert(list,3);
        System.out.println("revert: " + list);

    }
}
